package 回溯;
//https://leetcode.cn/problems/employee-importance/submissions/
import java.util.*;

public class 员工的重要性 {
    int num = 0;//辅助dfs方法记录结果
    public int getImportance(List<Employee> employees, int id) {
        return fun_DFS(employees , id);
        //return fun_BFS(employees , id);
    }
    //DFS方法也可以用hashMap进行操作
    public int fun_DFS(List<Employee> employees, int id) {
        for (Employee emp : employees){
            if (emp.id == id){
                List<Integer> sub = emp.subordinates;
                int imp = emp.importance;
                num += imp;
                for (int i = 0 ; i < sub.size() ; i ++ ){
                    fun_DFS(employees , sub.get(i));
                }
            }
        }
        return num;
    }
    public int fun_BFS(List<Employee> employees, int id){
        Map<Integer , Employee> map = new HashMap<>();
        for (Employee emp : employees){
            int eid = emp.id;
            map.put(eid , emp);
        }
        int num = 0;
        Queue<Employee> que = new ArrayDeque();
        que.offer(map.get(id));
        while(!que.isEmpty()){
            Employee emp = que.poll();
            num += emp.importance;
            List<Integer> sub = emp.subordinates;
            for (int eid : sub){
                que.offer(map.get(eid));
            }
        }
        return num;
    }
    class Employee {
        public int id;
        public int importance;
        public List<Integer> subordinates;
    }
}
